package com.fan.kmp;

import java.util.Arrays;

/**
 * kmp 算法
 * @author 19252
 */
public class Kmp {

    public static void main(String[] args) {
        Kmp demo = new Kmp();
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你";
        int i = demo.violentMatch(str1, str2);
        System.out.println(i);
        for (int j = 0; j < i; j++) {
            System.out.print(str1.charAt(j));
        }
        System.out.println();

        // String str1 = "BBC ABCDAB ABCDABCDABDE";
        // String str2 = "ABCDABD~";
        // String str2 = "AB";
        System.out.println(Arrays.toString(demo.kmpNext(str2)));
        System.out.println(demo.kmpMatch(str1, str2));
    }


    public int kmpMatch(String targetString, String  childString){
        int[] kmpNextArray = kmpNext(childString);

        int j = 0;
        int temp = 0;
        for (int i = 0; i < targetString.length(); ) {
            temp = i;
            // 使用全局变量移动下标
            while (targetString.charAt(temp) == childString.charAt(j)){
                temp ++;
                j ++;
                if (j == childString.length()){
                    return i;
                }
            }
            if (j > 0){
                // 跳过已经比较过的字符 kmp算法的思想 j - kmpNextArray[j - 1]
                // 是 i 移动多少步长就可以到达下一个相匹配的字符
                i = i + j - kmpNextArray[j - 1];
                // 将 j 置为 0 重新开始匹配判断
                j = 0;
            }else {
                // 如果一开始一个字符都没有匹配上 直接下移一位
                i ++;
            }
        }
        return -1;
    }


    public int[] kmpNext(String childString){
        // 创建一个数组保存部分匹配值
        int[] kmpNextArray = new int[childString.length()];
        // 首先只有一个字符的字符串的部分匹配值一定为0
        kmpNextArray[0] = 0;
        int index = 0;
        // ABCDABD
        // 后缀 i = 1 [BCDABD, CDABD, DABD, ABD, BD, D]
        // 前缀 index [A, AB, ABC, ABCD, ABCDA, ABCDAB]
        //       [0, 0, 0, 1, 2, 0]
        for (int i = 1; i < childString.length(); i++) {
            // 重新获取 j 的值 判断在当前的长为 i 的子串中的部分匹配值是多少
            while (index > 0 && childString.charAt(i) != childString.charAt(index)){
                index = kmpNextArray[index - 1];
            }
            // 对于各个子串来说，前缀的第一个字符与后缀的第一个字符能不能匹配至关重要
            // 如 子串 ABC，ABCD
            // 当 ABC 的后缀与前缀 包含在 ABCD 的后缀前缀中
            // 在比较ABC 时已经比较过的 字符 不用在ABCD中再次比较 ABC 后缀[BC, C] , ABCD 后缀 [BCD, CD, D]
            // 如果与 BC 中的B不匹配，那在 ABCD 中的最长后缀 BCD 就不需要 比较，直接进行 CD的比较
            if (childString.charAt(i) == childString.charAt(index)){
                index ++;
            }

            kmpNextArray[i] = index;
        }
        return kmpNextArray;
    }


    /**
     * 字符串暴力匹配算法
     * @param aimString 目标字符串
     * @param childString 子串
     * @return 如果目标串包含子串返回子串在目标串中的第一个匹配上的index
     */
    public int violentMatch(String aimString, String childString){
        char[] aimCharArray = aimString.toCharArray();
        char[] childCharArray = childString.toCharArray();

        int i = 0;
        int j = 0;
        int temp;
        while (true) {
            temp = j;
            while (true) {
                if (temp == aimCharArray.length){
                    return -1;
                }

                if (aimCharArray[temp] == childCharArray[i]) {
                    i++;
                    temp++;
                } else {
                    i = 0;
                    j++;
                    break;
                }

                if (i == childCharArray.length){
                    return j;
                }
            }
        }
    }
}
